package com.example.code2022;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: dangwen
 * @createDate: 2022/4/24
 * 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class P56 {
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{12, 19},{15,18}};

        System.out.println(JSON.toJSONString(intervals(intervals)));
    }

    public static int[][] intervals(int[][] ints){
        // 1.先对数组进行排序，根据数组中的第一个元素进行升序排序
        Arrays.sort(ints, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // 2.存放数组的结果集
        ArrayList<int[]> arrayList = new ArrayList<>();
        // 3.比较
        for (int i = 0; i < ints.length; i++){
            int[] arr = ints[i];
            // 第一个元素没有比较对象，直接放入容器。
            if (arrayList.isEmpty()){
                arrayList.add(arr);
            } else {
                // 和容器中的最后一个元素进行比较
                int[] intervalArr = arrayList.get(arrayList.size() - 1);
                int left= arr[0];
                // 如果此时数组左边的元素大于容器中数组右边的元素，说明无交集，直接放入容器
                if (left > intervalArr[1]){
                    arrayList.add(arr);
                } else{
                    int right = arr[1];
                    // 将最大的值赋值给容器中数组的右侧
                    intervalArr[1] = Math.max(right, intervalArr[1]);
                }
            }
        }
        return arrayList.toArray(new int[arrayList.size()][]);
    }
}
